\section{Algorithme de décision pour la distribution}
\label{Decision_algo}

A ce stade de la redistribution, trois ensembles sont construits et seront utilisés afin de décider comment sera réalisé la redistribution. L'algorithme présenté ici recevra donc, en entrée, l'ensembles des noeuds inchangés ($V_i$), celui des noeuds ajoutés ($V_a$) et celui des noeuds supprimés ($V_s$) et donnera, en sortie, une décision concernant la façon de redistribuer l'application. Il y a deux possibilités concernant la méthode de redistribution: \\

\begin{itemize}
	\item Ne redistribuer que ce qui a été ajouté, minimisant ainsi le coût de distribution de l'opération mais peut empirer le coût de transmission ;
	\item Distribuer ce qui a été ajouté et re-vérifier que le reste est toujours correctement distribués, ce qui permet de minimiser le coût de transmission mais augmente significativement le coût de distribution.
\end{itemize}

\bigskip
Afin d'y arriver, il faudra calculer ces deux coûts et les comparer mais, comme l'un se base sur un temps et l'autre sur un nombre de transmission, il va falloir trouver un moyen de les rendre comparables. \\

Cette section s'organisera de la façon suivante: tout d'abord une méthode de comparaison des deux coûts sera présentée, ensuite, le calcul de ceux-ci sera défini et, enfin, l'algorithme sera étudié et présenté. 

\subsection{Comparaison des coûts de transmission et de distribution}

Avant de se lancer dans le vif du sujet, il est important de rappeler la définition du coût de transmission ($C_T$) et celle du coût de distribution ($C_D$), comme vus dans la section~\ref{define-costs}: \\

\begin{itemize}
	\item $C_T = \sum_{i} \sum_{j} M_{ij}$ ; avec $M_{ij} = k$, $k$ étant le nombre de messages transmis entre les sites $S_i$ et $S_j$ ;
	\item $C_D = T$, T étant le temps nécessaire pour effectuer la distribution.
\end{itemize}

\bigskip
Comment évaluer ces valeurs de coûts ? Comment dire qu'un coût de transmission de X est supérieur à un coût de distribution de Y ? Afin de pouvoir comparer ou additionner les deux coûts (afin de mieux prendre une décision), il va falloir définir des valeurs par défaut. Pour le coût de distribution, il va falloir regarder chacun des cas possibles et assigner une valeur de coût pour ces cas, tandis que pour le coûts de transmission, il va juste falloir définir un coût par message et calculer le nombre de messages qui peuvent être transmis en une exécution du programme. Aussi, faut-il que les valeurs des coûts se valent, c'est-à-dire qu'un coût de distribution de 1 soit équivalent à un coût de transmission de 1, sinon la comparaison n'aurait aucun sens. \\

Dans la suite, tout d'abord, les valeurs des coûts de distribution seront donnés et expliqués, ensuite le coût de transmission d'un message sera défini ainsi que le moyen de calculer le nombre possibles de messages qui peuvent être transmis et, enfin, l'algorithme de prise de décision sera construit.

\subsubsection{Valeur des coûts de distribution}

Afin de mieux assigner les coûts, il faut identifier les différents cas de distribution possibles: \\

\begin{itemize}
	\item Les instructions utilisant une variable avec contrainte ;
	\item Les instructions utilisant une variable sans contrainte :
	\begin{itemize}
		\item et qui se trouve dans un bloc atomique avec contrainte ;
		\item et qui se trouve dans un bloc atomique sans contrainte ;
		\item et qui ne se trouve pas dans un bloc atomique.
	\end{itemize}
\end{itemize}

\bigskip
Pour le premier groupe d'instructions, comme il existe une contrainte sur la variable utilisée dans l'instruction (et donc, par définition, la contrainte s'applique à l'instruction), l'assignation est directe, sans choix possible. C'est pourquoi, pour ce groupe-ci, \textbf{le coût de distribution est fixé à 1}. \\

Pour le second groupe d'instructions, aucune contrainte n'est imposée sur l'instruction elle-même, mais elle se trouve dans un bloc atomique sur lequel une contrainte est imposée (c'est-à-dire qu'il contient une variable sur laquelle est imposée une contrainte). Par définition, cette instruction doit se trouver sur le même site que la variable utilisée dans ce bloc atomique. Ici, également, aucun choix n'est possible donc \textbf{le coût de distribution est fixé à 1}. \\

Pour le troisième groupe, étant donné qu'aucune contrainte n'est imposée, ni sur l'instruction elle-même, ni sur son bloc atomique, le choix du site est libre et, par conséquent, \textbf{le coût de distribution est fixé à 1}. \\
Parfois, il pourrait être intéressant d'équilibrer la charge de travail des différents sites et de distribuer ces instructions sur les sites qui ont le moins de charge de travail. Cependant, dans ce travail, nous faisons abstraction de ce détail, ce qui nous évite d'introduire un coût en plus et de compliquer encore plus l'algorithme de décision. Le lecteur pointilleux pourra imaginer la prise en compte de cette optimisation. \\

Enfin, pour le dernier groupe d'instructions, il va falloir regarder les instructions autour des instructions qui sont en train d'être colorées afin de réduire le coût de transmission. Du fait de cette analyse à faire, \textbf{le coût de distribution est fixé à 3}. 

\subsubsection{Valeur du coût de transmission d'un message}

Le coût de transmission d'un message est relativement difficile à évaluer. En effet, le temps que cela prend dépend de la distance entre les deux sites qui s'envoient des messages et, comme c'est une information inconnue au moment de la distribution, il serait impossible d'évaluer correctement un coût pour les transmissions. C'est pourquoi le coût d'envoi d'un message est choisi arbitrairement, sans raisons particulières. Pour ce travail, le \textbf{coût de transmission d'un message est fixé à 5}


\subsection{Calcul des coûts de transmission et de distribution}

\subsubsection {Calcul du coût de distribution}

Ce que nous avons, c'est trois ensembles d'instructions: l'ensemble des instructions inchangées, $V_i$, l'ensemble des instructions ajoutées $V_a$ et l'ensemble des noeuds supprimés $V_s$. Le calcul de ce coût revient alors à considérer chaque instruction dans $V_a$, de regarde de quel type d'instruction il s'agit (selon la classification faite à la section précédente) et d'ajouter son coût au coût de distribution total. \\

Une remarque à faire sur cette méthode est que ceci donne un coût de distribution optimal (puisqu'on ne distribue que ce qui a été ajouté) mais, dans l'algorithme de redistribution, il va peut-être falloir vérifier certains noeuds, ce qui fera augmenté le coût total de distribution. Tout ceci sera expliqué plus en détail dans la section~\ref{algo-decision} dans laquelle les coûts évolueront par itération.

\subsubsection {Calcul du coût de transmission}

Pour calculer le coût de transmission, il va d'abord falloir calculer le nombre de messages qui peuvent être transmis durant l'exécution du programme~\footnote{Comme le programme s'exécute dans une boucle, seul le premier tour sera considéré, ici.}. Pour ce faire, il va falloir recourir à l'utilisation de graphe de contrôle de flot. Les définitions intuitive et formelle d'un graphe de contrôle de flot ont été données dans la section~\ref{distrib_algo_second_step}. C'est ce même graphe qui sera utilisé et pour calculer le nombre de messages transmis, il suffit d'additionner les pondérations des arcs entre les noeuds de différente couleur. \\

Une remarque doit être précisée concernant la construction du graphe de contrôle de flot. Dans ce cas-ci, la redistribution, il ne faut pas considérer toutes les instructions mais uniquement les instructions qui se trouvent dans l'ensemble des noeuds ajoutés, $V_a$. En effet, comme cela a été expliqué dans la section~\ref{section-compare-graph}, les noeuds séquentiels ne peuvent pas être identifiés uniquement et sont donc automatiquement considérés comme étant des ajouts. Ceci étant dit, vu la nature d'un programme de contrôle qui consiste à réagir à des évènements, la plupart du code d'une telle application sera constituée de blocs atomiques et donc le fait de considérer l'ensemble des instructions séquentielles comme étant des ajouts n'augmente pas (trop) la coût de distribution.

\subsubsection{Exemple de calcul des coûts}

\todo{créer exemple avec IF, WHILE, etc}

\subsection{Algorithme de décision relative à la méthode de distribution}
\label{algo-decision}